/*
 * @lc app=leetcode.cn id=23 lang=cpp
 *
 * [23] 合并K个升序链表
 */

#include <limits.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
   public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return mergeKLists(lists, 0, lists.size() - 1);
    }

    ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right) {
        if (left > right) return nullptr;
        if (left == right) return lists[left];

        int mid = (left + right) / 2;
        return mergeTwoLists(mergeKLists(lists, left, mid),
                             mergeKLists(lists, mid + 1, right));
    }

    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        ListNode* head = new ListNode();  // 伪头部
        ListNode* result = head;
        ListNode* aPtr = a;
        ListNode* bPtr = b;

        while (aPtr != nullptr && bPtr != nullptr) {
            if (aPtr->val < bPtr->val) {
                head->next = aPtr;
                aPtr = aPtr->next;
            } else {
                head->next = bPtr;
                bPtr = bPtr->next;
            }
            head = head->next;
        }

        if (aPtr != nullptr) {
            head->next = aPtr;
        } else {
            head->next = bPtr;
        }

        return result->next;
    }
};
// @lc code=end
